Scroll Progress Bar

Recursive Functions

A recursive function is a function that calls itself to solve a problem. It is a porful programming technique used to break a complex problem into smaller sub-problems. Each recursive call reduces the original problem towards a base case where no further recursion is needed.

Usage and Principle:

Recursive functions are particularly useful for problems that exhibit self-replicating structures or have sub-problems that resemble the original problem. To avoid infinite recursion, every recursive function must have a base case that stops the recursion.

Sample Code with Explanation and Output:

In this example, 'll implement a recursive function to calculate the factorial of a non-negative integer. 


#include <stdio.h>

// Recursive function to calculate factorial
unsigned long long int factorial(int n) {
    // Base case: factorial of 0 is 1
    if (n == 0) {
        return 1;
    }
    // Recursive case: factorial(n) = n * factorial(n-1)
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    unsigned long long int result = factorial(num);
    printf("Factorial of %d is: %llu\n", num, result);
    return 0;
}
Output:

Factorial of 5 is: 120
Explanation:
  • The sample code contains a recursive function factorial() that calculates the factorial of a non-negative integer n.
  • The base case of the recursive function is when n is 0, in which case the function returns 1.
  • For non-zero n, the function recursively calls itself with the argument n - 1, effectively breaking the problem into smaller sub-problems until the base case is reached.
  • Each recursive call returns the factorial of a smaller value, and the final result is calculated by multiplying the current value n with the result of the recursive call.
  • In the main() function, call factorial() with num set to 5 and print the result.
Key Points:
  • Recursive functions should always have a base case to terminate the recursion.
  • Recursive calls should lead to a smaller or simpler problem than the original one.
  • Proper termination of recursion is essential to avoid infinite recursion and stack overflow.

What is recursion in C?

Function

What is a base case in recursion?

Terminating

What is a recursive function's calling itself?

Recursion

What is a recursive function's intermediate result?

Subproblem

What is a recursive function's control stack?

Call